// https://leetcode.cn/problems/sliding-window-maximum/description/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 单调队列维护滑动窗口最大值
// 2. 队列头部始终保持当前窗口最大值的索引
// 3. 入队时移除尾部所有小于当前值的元素
// 4. 检查并移除超出窗口范围的头部元素
// 5. 时间复杂度：O(n)，空间复杂度：O(k)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <deque>

class Solution 
{
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) 
    {
        int m = nums.size();

        deque<int> dq;
        vector<int> ret;

        for (int i = 0 ; i < m ; i++)
        {
            while (!dq.empty() && nums[dq.back()] <= nums[i])
            {
                dq.pop_back();
            }
            dq.push_back(i);

            if (dq.front() == i - k)
            {
                dq.pop_front();
            }

            if (i >= k - 1)
            {
                ret.push_back(nums[dq.front()]);
            }
        }

        return ret;
    }
};

int main()
{
    vector<int> nums1 = {1,3,-1,-3,5,3,6,7};
    vector<int> nums2 = {1};
    int k1 = 3, k2 = 1;

    Solution sol;

    auto v1 = sol.maxSlidingWindow(nums1, k1);
    auto v2 = sol.maxSlidingWindow(nums2, k2);

    for (const int& num : v1)
        cout << num << " ";
    cout << endl;

    for (const int& num : v2)
        cout << num << " ";
    cout << endl;

    return 0;
}